For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

Approach 1 - Tries

If the user types the partial query "What", then we must show the top 5 search queries that are a strict prefix match.

Each trie node will store

1. children (all the subsequent letters)
2. isTerminal
3. count (only if isTerminal — the number of times this search query has been searched)

class TrieNode {

    TrieNode children[63]    // a-z + A-Z + 0-9 + space

    long count;              // how many times has this

                             // query been searched

}

Queries

typeahead(partialQuery)

1. go to the node that matches the partialQuery

1. start from root
2. for each letter of the partialQuery, we will go to the appropriate child

2. Once we've reached the matching node, all the possible suggestions are within the subtree of this node
3. We will have to go through the entire subtree (all possible suggestions that match the prefix), and find the top 5

Going through the entire subtree of a node will be highly time consuming

There's potentially billions of entries in that subtree!

Can improve this by "data-augmentation"

At every node, pre-compute & store the top 5 results.

In this case, the updates will become (slightly) slow

log_search(searchQuery)

(update the count for this query)

1. traverse to the node that matches this searchQuery
2. increment the count
3. (if augmented, then also update the data for all nodes till root)

Sharding

Q: What will be the sharding key?

1. First letter: every query that starts with the letter a will go to the same shard
   this doesn't mean that the starting letter a must get a dedicated shard - a single shard might contain multiple starting letters. We're just saying that all queries that start with the letter a must definitely go in the same shard.

1. 
2. Low cardinality (only 26 possible children)
3. Uneven data distribution
   number of queries starting with a will be much higher than the number of queries starting with z

2. First 3 letters: every query that starts with the letters abc will go to the same shard
   this doesn't mean that the starting letters abc must get a dedicated shard - a single shard might contain multiple starting letters. We're just saying that all queries that start with the letters abc must definitely go in the same shard.

1. 
2. High cardinality: 263 ~= 17000
3. Uneven data distribution
   number of queries starting with why will be much higher than the number of queries starting with zxz

1. to fix the load distribution, we will have to manually create groups of starting 3 letters in order to club the less frequent queries together
2. number of queries starting with why will be much higher => dedicated shard
3. number of queries starting with zxz will be lower in count, so we will group them with other rare starting letters zyx + zxy + zxz + ..
   

Q: Which existing Databases support this?

There's no popular database that was built for storing tries!

Tries exist as an 3rd party extension in some popular databases. However, no database was built specifically to store tries.

So you must build your own DB.

Approach 2 - Hashmap / Key-Value

As a DSA person, we would create a Trie, and augment the TrieNode with data. This data will store the top 5 suggestions for each TrieNode.

As a HLD person, we will realize that effectively, we’re just caching the top-5 results for each possible “prefix”.

• prefix == TrieNode
• data-augmentation == cache

So we can store this as a separate cache!

Queries

typeahead(partial_query)

If someone types "what i" then we can just go to the suggestions db, and look up that partialQuery.

This will be very fast

1. hashmaps have O(1) lookup

1. in reality, the complexity is O(l) where l is the length of the key. But the assumption is that your keys in a hashmap should NEVER be long. If your hashmap keys are long, then you’re using hashmaps incorrectly.
2. in our case, the average key length was assumed to be 10 chars, and the max length was assumed to be 50 chars 

2. we don't need any computation / processing - we just have to get the value for the given key from the key-value DB

We needed ultra low latency (< 10ms), and, high read throughput (10 million reads / second at peak)

• Redis lookup has latency of <= 1ms
• A single redis server can easily handle 100,000+ reads/writes per second!

• just need ~100 redis servers
  (google has over 10 million servers - as of 2020)

log_search(search_query)

Whenever someone searches for a query "what does the fox say"

1. I need to update the count in the search frequency database

• super simple - just call redis.inc(searchQuery)

2. I need to update the cache (top suggestions database)

• what all entries do I need to update?

1. If I'm updating the count for what does the fox say then is it possible for the suggestions of the prefix "how" to get changed?
   No.
2. What prefixes will get effected?
   only the prefixes of the search query
   wha
   what
   what d
   ...
   what does the fox
   what does the fox s
   what does the fox sa
   what does the fox say
3. How many such prefixes (on average) need to be updated?
   the average query is 10 letters. So ~10 prefixes on average need to be updated.
   but this now means, that for each update, I must do 1 + 10 writes
   total number of writes in redis
   = (1 million log_search / sec) * 11 writes / log_search
   = 11 million writes / second
   this makes my system both read & write heavy!
   no db in the world that is optimized for both reads & writes

Sharding

Sharding is automatic - based on the hash(key)

Q: Are there databases that have 1st class support for hashmaps?

Yes. Not just 1 - there's an entire category!

Q: Which existing Databases support this?

Key-Value databases are basically just hashmaps that are distributed across servers.

Redis / Memcached / DynamoDB / ...

Optimizing the System

If the system is Read Heavy (not write heavy)

• If eventual consistency is okay, then ⇒ absorb the reads in the cache, and optimize the DB for writes.
• If immediate consistency is needed, then ⇒

• either incur extra write latency by using a write-through cache, and your DB will be optimized for writes.
• or, optimize the DB for reads. In this case, the writes will be slower, but that’s okay because the writes are less. Both reads & writes now go to the DB. This will be slower than the cached approach.

If the system is Write Heavy (not read heavy)

• Irrespective of eventual vs immediate consistency ⇒ optimize the DB for writes.

• If your reads are significant, you can absorb the reads in the cache. If not significant, then let them go to the DB, and let the reads be slow.
• Your cache cannot handle the writes – because that would lead to data loss, if the cache server crashes with unsynced changes (write-back cache)

If the system is both read & write heavy

• very VERY difficult!
• Either you can somehow “reduce” the writes

• Batching — forces eventual consistency

• wait for a bunch of requests to collect, and then we will process them in 1 go.

• Sampling — forces data loss

• don’t process all the requests.. process only some of the requests

• If you cannot reduce the writes, then you need to shard more

• sharding improves both reads & writes!
• but then, you can’t join across shards efficiently

• if some query needs data from multiple shards, that will be slow

Optimizing Writes

We can reduce the number of writes significantly, because, we can afford eventual consistency & data loss (non-functional requirements)

Batching / Batch Processing

Instead of doing each task 1 by 1, you wait for a lot of tasks to pile up. And then you do all of them in 1 go as a batch.

Example: if you have 10 guests at your house, and you need to need to serve tea

1. make a cup of tea, serve it. Make next cup of tea, serve it.. individual request processing
2. make a batch of tea in 1 go.. and then serve it together: Batching!

Whenever we get a log_search(search_query) request, instead of updating the suggestions db immediately, we wait for the count to increase by a fixed amount (say 1000)

Earlier

fn log_search(search_query):       // 1 million qps

    frequency_db.inc(search_query) // 1 million writes/s

    update_prefixes(search_query)

fn update_prefixes(search_query):

    for i = 3 ... len(search_query) - 1 // 10 iterations

        prefix = search_query[:i]

        ... logic to update the suggestions list

            in the suggestions db

        // 10 million writes/s

Batching

fn log_search(search_query):       // 1 million qps

    updated_count = frequency_db.inc(search_query)

    // 1 million writes/s

    if updated_count % 1000 == 0:

          // update the prefixes only if the count

          // has changed by the batch size

    update_prefixes(search_query)

fn update_prefixes(search_query):

    ...   // (1 million / 1000 qps) * 10 updates

          // 10,000 writes/sec

Effectively, we will only update the suggestions when the count increases by 1000.

Earlier, we had

1 million writes/sec (freq db)

+ 10 million writes/sec (suggestions db)

total = 11 million writes/sec

After batching

1 million writes/sec (freq db)

+ (10 million / 1000) writes/sec (suggestions db)

total = 1.01 million writes/sec

Note: we cannot make the number of writes less than 1 million per second, because that's the number of times we've the update at least the counts in the frequency database.

Note: batching doesn't cause data loss (freq data is always up-to-date) — it just causes delays (stale reads) in the suggestions updates.

Sampling

Exit polls during elections

1. country-wide election: 1 crore voters
2. the actual counting will take several days
3. News channels want to predict the winner with high accuracy before the actual results are announced
4. The news channels will ask various people "who did you vote for" and they will create their own voting list & winners
5. Can the news channels talk to all the 1 crore voters?
   No.
6. They stand in front of a small fraction of the polling booths
   As the people exit the booths, they will ask a few random people "who did you vote for"
7. They will only use this small subset/sample of data to "estimate" the winner
8. if the news channel is unbiased their exit poll results will almost perfectly match the actual election results

If you draw an unbiased sample from a population, then any trends that hold within the population will also hold within the sample.

Typically a good way of getting unbiased samples is to just sample uniformly at random.

Note: Sampling can cause data loss of individual data points. But it won't lose the overall trends. (use it only when data loss is okay)

Earlier

search service

fn search(query):

    ...

    make an API call to typeahead service's log_search endpoint

typeahead service

    fn log_search(search_query):

        frequency_db.inc(search_query)

        update_prefixes(search_query)

    fn update_prefixes(search_query):

        for i = 3 ... len(search_query) - 1

            prefix = search_query[:i]

            ... logic to update the suggestions list

                in the suggestions db

Sampling

search service

fn search(query):

    ...

    if rand() < 0.001:

        // with a probability of 0.1% make the following call

 make an API call to typeahead service's log_search endpoint

typeahead service

     ...

For 99.9% of the searches, we're not even updating the counts (just ignore them)

For a random 0.1% of the searches, we're calling the log_search and we will update both the counts & the suggestions.

Thanks to sampling, instead of having 1 million + 10 million writes/second, we now come back to just (1 million + 10 million) / 1000  =  10,000 writes / second

Q: Won't the counts be inaccurate?

Yes. Effectively, each count is being divided by approx. 1000 (but not exactly - it's random)

Q: Won't the suggestions be not exactly in order?

Yes.

But none of that matters. Because still, the suggestions shown to the users will continue to be highly relevant!

Q: If we use sampling, then won’t infrequent queries have very low counts / might completely be missed out from the database?

Yes, that can happen! That’s a feature, not a bug!

A rare query will never be a part of typeahead suggestions anyway (because it is not popular)

Effectively, sampling has automatically reduced your data massively by removing the majority (99.9%) of the bad queries 🙂

Future Scope

Recency Factor

Problem Statement

Suppose there's a big event that happens

• COVID lockdown gets declared
• Election results are out
• Some high profile person got arrested
• Federer won the Wimbledon
• ...

This is a trending event.

Even though "why is the sky blue?" might have a higher overall count, but since the query "what happened in Nepal?" is trending (recent + popular), we should rank that higher when someone types "wh"

Approach - 1

Maintain separate counts for latest week/month!

For each query, we maintain three counts.

1. Total Count
2. Last Week Count
3. Last Day Count

total:why is the sky blue?    ⇒ 5000

 week:why is the sky blue?    ⇒  200

  day:why is the sky blue?    ⇒   50

total:what happened in Nepal? ⇒  500

 week:what happened in Nepal? ⇒  300

  day:what happened in Nepal? ⇒  100

To find the top-k suggestions

1. Find top-k from total
2. Find top-k from weekly
3. Find top-k from daily
4. Merge the results based on some scoring function

Goal

give more weightage to the recent counts

Solution

Simply decay the historical counts after every fixed period of time.

After each day, decrease the total count for each query by 10%

"who has control over nukes?"

[1000, 1000, 1000, 1000, ... 1000] => total is 100,000

day 1: 1000

day 2: 90% of 1000 + 1000 => 1900

day 3: 90% of 1900 + 1000 => 2710

day 4: 90% of 2710 + 1000 => 3439

...

day 100:  => 1000 + 1000 * 0.9 + 1000 * 0.92 + ...

          => 1000 * (1 + 0.9 + 0.92 + 0.93 + ...)

          => 1000 * 1 / (1 - 0.9)

          => 10,000

"who won the wimbledon"

[0, 0, 0, ... , 5000, 5000, 5000] => total is just 15000

day 97: 0

day 98: 5000

day 99: 5000 * 0.9 + 5000 => 9,500

day 100: 9500 * 0.9 + 5000 => 13,550

If the count after decay reduces below a threshold (say 0) then we can remove that entry.

Geolocation based personalization

Given the user's request, find out their location based on ip address.

Build a separate database for each location ⇒ shard the DB by country_id

Now an Indian user's request will only go to the Indian shard.

“global:what does the fox say”  ⇒ 1000

“India:what does the fox say” ⇒ 10

“USA:what does the fox say” ⇒ 10

When an Indian user types “wha”

Find the suggestions for, “wha” prefix, and the suggestions for “India:wha” prefix, we will merge the results, and then return the final set.

User based personalization

Do this purely on the client side.

The browser stores the user's search/browsing history.

1. browser will create typeahead suggestions from the user's local data
2. browser will initiate a backend request to get the global typeahead suggestions
3. browser will merge these two lists

Google actually pulls this from the backend too – because it does maintain your search & browsing history in the backend DB.

Handling Typos

Whenever a search is made, apart from updating the count of the search_query, you also update the count of the spell_corrected(search_query)

Whenever a user types something, you find the suggestions for partial_query, but you also include the suggestions for spell_corrected(partial_query)

def spell_corrected(input: str) ⇒ str:

    ”””Corrects the spellings of the words within

       the input string, and returns the corrected

       string.

       Note:

           - each word in the input is spell corrected

           - gracefully handles partial words

    “””

You can simply have a dictionary and you can calculate the “edit-distance” b/w the user’s words and the words in the dictionary.

Peter Norvig — How to Write a Spelling Corrector        

Resources

1. Spelling correction: https://norvig.com/spell-correct.html